package Tree;


import java.util.*;

public class L94_二叉树遍历 {
    //递归的实现都在后面

    /**
     *  多一个来记录是否遍历过
     */
    public List<Integer> postorderTraversal_queue(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return list;
        TreeNode curr, pre=null;

        stack.push(root);
        while ( !stack.isEmpty()){
             curr = stack.peek();//获取元素，但是不移除，pop 才是移除
            if( (curr.left == null && curr.right == null) || //这个条件是因为访问到根节点了
                    (pre != null && (pre == curr.left || pre == curr.right))){//前一个节点是否跟当前节点左右一样，是的话，就说明也到目前这个元素了
                //如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时，当前结点出栈
                list.add(curr.val);
                pre = curr;
                stack.pop();
            }else{
                if(curr.right != null) stack.push(curr.right); //先将右结点压栈
                if(curr.left != null) stack.push(curr.left);   //再将左结点入栈
            }
        }
        return list;
    }

    /**
     * 前序遍历
     */
    public List<Integer> preorderTraversal_非递归(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return list;
        TreeNode p;
        stack.push(root);
        while (!stack.isEmpty()){
            p = stack.pop();
            list.add(p.val);
            //记住，要先右，再左，不然，对于 3,1,2 会有问题
            if(p.right != null){
                stack.push(p.right);
            }
            if(p.left != null){
                stack.push(p.left);
            }
        }
        return list;
    }

    /**
     * 用stack来实现中序， stack的方式遍历 跟翻转二叉树的queue的后续遍历是不一样的，注意区别
     */
    public List<Integer> inorderTraversal_非递归(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        TreeNode p = root;
        while (p != null || !stack.isEmpty()){
            if(p != null){
                stack.push(p);//这个是当前节点， 不是 push右节点，因为右节点会在下面遍历的时候放在最后遍历
                p = p.left;
            }else{
                p = stack.pop();
                list.add(p.val);
                p = p.right;
            }
        }
        return list;
    }

    //下面全是递归的，都很简单
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        return list;
    }
    void inOrder(TreeNode root, List<Integer> list){
        if(root == null) return ;
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preOrder(root, list);
        return list;
    }
    void preOrder(TreeNode root, List<Integer> list){
        if(root == null) return ;
        list.add(root.val);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }

}
